//
//  Offer_07.swift
//  LeetCode
//
//  Created by migu on 2020/12/10.
//  Copyright © 2020 LBB. All rights reserved.
//  剑指 Offer 07. 重建二叉树

//输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

//例如，给出
//前序遍历 preorder = [3,9,20,15,7]
//中序遍历 inorder = [9,3,15,20,7]
//         3
//       9   20
//         15   7

//返回如下的二叉树：
//   3
//  / \
// 9  20
//   /  \
//  15   7


import Foundation
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init(_ val: Int) {
 *         self.val = val
 *         self.left = nil
 *         self.right = nil
 *     }
 * }
 */

class Offer_07 {
    var count:Int = 0;
    var pre:Int = 0;
    
    func buildTree(_ preorder: [Int], _ inorder: [Int]) -> TreeNode? {
        var treeNode = TreeNode(0, nil, nil)
        if preorder.count == 0 || inorder.count == 0 {
            return nil
        }
        treeNode = buildChildTree(preorder, inorder, 0) ?? TreeNode(0, nil, nil)
        return treeNode
    }
    
    func buildChildTree(_ preorder: [Int], _ inorder: [Int], _ stop: Int) -> TreeNode? {
        if pre >= preorder.count {
            return nil
        }
        if inorder[count] == stop {
            count += 1
            return nil
        }
        let treeNode = TreeNode(preorder[pre], nil, nil)
        pre += 1
        let leftTree = buildChildTree(preorder, inorder, treeNode.val)
        let rightTree = buildChildTree(preorder, inorder, stop)
        treeNode.left = leftTree
        treeNode.right = rightTree
        return treeNode
    }
    
    func getChildTree(_ childTree: TreeNode,_ preorder: [Int], _ inorder: [Int]) -> TreeNode? {
        let left = TreeNode(0, nil, nil)
        let right = TreeNode(0, nil, nil)
        let val = childTree.val
        childTree.left = left
        childTree.right = right
        //前序遍历中的下一个节点
        var nextVal = Int()
        //前序遍历中的下下一个节点
        var nextnextVal = Int()
        //获取根节点所在前序遍历的位置
        let preorderValIndex:Int = preorder.firstIndex(of: val) ?? 0
        if (preorderValIndex + 1) < preorder.count {
            nextVal = preorder[preorderValIndex+1]
        }
        if (preorderValIndex + 2) < preorder.count {
            nextnextVal = preorder[preorderValIndex+2]
        }
        //获取根节点所在中序遍历的位置
        let valIndex:Int = inorder.firstIndex(of: val) ?? 0
        //获取根节点的下一个节点所在中序遍历的位置
        let nextValIndex:Int = inorder.firstIndex(of: nextVal) ?? -1
        //获取根节点的下下一个节点所在中序遍历的位置
        let nextnextValIndex:Int = inorder.firstIndex(of: nextnextVal) ?? -1
        //获取整个二叉树根节点所在中序遍历的位置
        let rootValIndex = inorder.firstIndex(of: childTree.val) ?? 0
        
        if nextValIndex == -1 {
            return childTree
        } else {
            if valIndex > nextValIndex {
                left.val = nextVal
                getChildTree(left, preorder, inorder)
            } else {
                right.val = nextVal
                getChildTree(right, preorder, inorder)
            }
        }
        if nextnextValIndex > valIndex && nextnextValIndex > rootValIndex {
            right.val = nextnextVal
            getChildTree(right, preorder, inorder)
        }
        return childTree
    }
}
